About the Journal

Proceedings of the YSU A: Physical and Mathematical Sciences aims to publish original research papers and survey articles in all areas of physics, mathematics and informatics. Proc. YSU A: Phys. Math. Sci. accepts also review articles, short communications, conference proceedings, algorithms, Ph.D and doctoral thesis’s and other items with a detailed exposition of results, proofs, experiments and examples. One of purposes is to reflect the progress of the research in all areas of physics, mathematics and informatics in Armenia and, by providing an international forum, to stimulate its further developments. 

Current Issue

Vol. 60 No. 2 (270) (2026): In process
DOI: https://doi.org/10.46991/PYSUA.2026.60.2
Published: 2026-06-16

Mathematics

  • Mathematics

    ON EDGE-CHROMATIC SUMS OF CORONA PRODUCTS OF GRAPHS

    Hamlet V. Mikaelyan, Petros A. Petrosyan
    View PDF
    Abstract

    A proper edge-coloring of a graph $G$ is a mapping from its edges to the set of positive integers, so that adjacent edges receive different numbers (colors). If a proper edge-coloring of a graph $G$ minimizes the sum of colors on all edges, it is called a sum edge-coloring and the sum is called the edge-chromatic sum of $G$. In this paper, we study the connection between the edge-chromatic sum of corona product of graphs with the edge-chromatic sums of its factors.  We provide general upper bounds on the edge-chromatic sum of corona products of graphs, as well as we prove that the edge-chromatic sum of the corona products of bipartite graphs and regular graphs of odd order can be exactly determined by the edge-chromatic sums of the factors.

    References

    West D.B. Introduction to Graph Theory. Prentice-Hall, New Jersey (2001). https://dwest.web.illinois.edu/igt/

    Supowit K.J. Finding a Maximum Planar Subset of a Set of Nets in a Channel. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. 6 (1987), 93-94. https://doi.org/10.1109/TCAD.1987.1270250

    Kubicka E. The Chromatic Sum and Efficient Tree Algorithms. PhD Thesis. Western Michigan University (1989).

    Giaro K., Janczewski R., et al. A 27/26-approximation Algorithm for the Chromatic Sum Coloring of Bipartite Graphs. Lecture Notes in Computer Science. 2462 (2002), 135-145. https://doi.org/10.1007/3-540-45753-4_13

    Jansen K. The Optimum Cost Chromatic Partition Problem. Algorithms and Complexity. Springer, Berlin (1997), 25-36.

    Kubicka E., Kubicki G., Kountanis D. Approximation Algorithms for the Chromatic Sum. In: Lecture Notes in Comput. Sci. 507 (1991), 15-21. https://doi.org/10.1007/BFb0038467

    Malafiejski M., Giaro K., et al. Sum Coloring of Bipartite Graphs with Bounded Degree. Algorythmica 40 (2004), 235-244. https://doi.org/10.1007/s00453-004-1111-4

    Thomassen C., Erdos P., et al. Tight Bounds on the Chromatic Sum of a Connected Graph. J. Graph Theory 13 (1989), 353-357. https://doi.org/10.1002/jgt.3190130310

    Lecat C., Lucet C., Li C.-M. New Lower Bound for the Minimum Sum Coloring Problem. In: Proc. AAAI Conf. Artificial Intelligence (2017), 853-859. https://doi.org/10.1609/aaai.v31i1.10661

    Moukrim A., Sghiouer K. et al. Upper and Lower Bounds for the Minimum Sum Coloring Problem. International Symposium on Combinatorial Optimization (ISCO2010) (2013).

    Hajiabolhassan H., Mehrabadi M.L., Tusserkani R. Minimal Coloring and Strength of Graphs. Discrete Math. 215 (2000), 265-270. https://doi.org/10.1016/S0012-365X(99)00319-2

    Bar-Noy A., Bellare M., et al. On Chromatic Sums and Distributed Resource Allocation. Inform. and Comput. 140 (1998), 183-202. https://doi.org/10.1006/inco.1997.2677

    Salavatipour M.R. On Sum Coloring of Graphs. Discrete Appl. Math. 127 (2003), 477-488. https://doi.org/10.1016/S0166-218X(02)00249-4

    Marx D. Complexity Results for Minimum Sum Edge Coloring. Discrete Appl. Math. 157 (2009), 1034-1045. https://doi.org/10.1016/j.dam.2008.04.002

    Giaro K., Kubale M. Edge-Chromatic Sum of Trees and Bounded Cyclicity Graphs. Inform. Process. Lett. 75 (2000), 65-69. https://doi.org/10.1016/S0020-0190(00)00072-7

    Petrosyan P.A., Kamalian R.R. On Sum Edge-Coloring of Regular, Bipartite and Split Graphs. Discrete Appl. Math.bf 165 (2014), 263-269. https://doi.org/10.1016/j.dam.2013.09.025

    Mitchem J., Morriss P., Schmeichel E.F. On the Cost Chromatic Number of Outerplanar, Planar, and Line Graphs. Discuss. Math. Graph Theory 17 (1997), 229-241. https://doi.org/10.7151/DMGT.1050

    Frucht R., Harary F. On the Corona of Two Graphs. Aequationes Math. 4 (1970), 322-325. https://doi.org/10.1007/BF01844162

    Sharma R., Adhikari B., Mishra A. Structural and Spectral Properties of Corona Graphs. Discrete Appl. Math. 228 (2017), 14-31. https://doi.org/10.1016/j.dam.2017.01.005

    Arumugam S., Lee Yi-Chun et al. On Local Antimagic Vertex Coloring for Corona Products of Graphs. Combinatorics (2018). https://arxiv.org/abs/1808.04956

    Thiru V.S., Balaji S. Strong Chromatic Indices of Certain Binary Operations on Graphs. Discrete Math. Algorithms Appl. 16 (2024), 2350073. https://doi.org/10.1142/S1793830923500738

    Izbicki H. Zulässige Kantenfärbungen von Pseudo-regulären Graphen mit Minimaler Kantenfarbenzahl. Monatsh. Math. 67 (1963), 25-31. https://doi.org/10.1007/BF01300678

View All Issues